НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №3 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «МЕТОДИ СОРТУВАННЯ» Варіант 13  Київ 2022 Мета: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Теоретичні відомості Сортування вибором — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність n2, що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритм сортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю. Сортування включенням або сортування вставлянням — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг: 1 - простота у реалізації 2 - ефективний (зазвичай) на маленьких масивах 3 - ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій 4 - на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною 5 - є стабільним алгоритмом. Наприклад, більшість людей при сортуванні колоди гральних карт, використовують метод, схожий на алгоритм сортування включенням. Сортування злиттям (англ. merge sort) — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй». В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової. Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так доти, доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме доти, доки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.  / / Сортування вставками + додатково вибором. /  Результат роботи Виконання алгоритму масиву лише 10 * 10 / Також розмірність звеличина до 1000 * 1000 для аналізу різниці швидкостей: / Висновки: розроблено програму, що виконує два рази той же самий алгоритм в основі якого лежить сортування, але з різницею в методах сортування. Перший раз використано алгоритм сортування вставкою, а наступний алгоритм вибором. У результаті порівняно час, затрачений на різні методи сортування, і виявилося, що сортування вставками швидше на 6 мілісекунд, ніж сортування вибором. Програмний код public class Lr3{ public static void main(String[] args) { int side = 10; int[][] arr = generateArr(side); int[][] arrCopy = copyArr(arr); System.out.println("Дано масив розмірностю " + side + ":"); displayArr(arr); System.out.println("\nВиконання сортування вставками:"); long time = System.currentTimeMillis(); for (int j = side-1; j > 0; j--) { int[] subArr = new int[j]; for (int i = (side-1 - j) + 1; i < side; i++) { s...